package cn.lintcode;

import java.util.Arrays;
import java.util.Collections;
import java.util.Random;

/**
 * @author labvi
 * @version 1.0.0
 * 找中位数
 */
public class FindMedian {

    public int median(int[] nums) {
        if (nums == null || nums.length<1) {
            return -1;
        }
        if (nums.length <2) {
            return nums[0];
        }
//        return sub(nums,0,nums.length-1,(nums.length - 1)>>1);
        return sub(nums, 0, nums.length - 1, (nums.length + 1)/2);
    }

    private int sub(int[] nums, int start, int end, int size) {
        int mid = (start + end) / 2;
        int pivot = nums[mid];
        int i = start - 1, j = end + 1;
        for (int k = start; k < j; k++) {
            if (nums[k] < pivot) {
                i++;
                int tmp = nums[i];
                nums[i] = nums[k];
                nums[k] = tmp;
            } else if (nums[k] > pivot) {
                j--;
                int tmp = nums[j];
                nums[j] = nums[k];
                nums[k] = tmp;
                k--;
            }
        }
        if (i - start + 1 >= size) {
            return sub(nums, start, i, size);
        } else if (j - start >= size) {
            return nums[j-1];
        } else {
            return sub(nums, j, end, size - (j - start));
        }
    }

    /*public int sub(int[] nums,int start,int end,int size){
        int mid = start + (end - start) /2;
        int pivot = nums[mid];
        int i = start -1,j = end + 1;
        for (int k = start;k < j;k++){
           if (nums[k] < pivot) {
               i++;

           } else if (nums[k] > pivot) {
               j--;
               int tmp = nums[j];
               nums[j] = nums[k];
               nums[k] = tmp;
               k--;
           }
        }

        if (i - start>size) {
            return sub(nums,start,i,size);
        } else if (j - start > size) {
            return nums[j-1];
        } else {
            return sub(nums,j,end,size - (j-start));
        }
    }*/


    public int[] generator(int maxSize,int maxValue){
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        Random random = new Random();
        for (int i = 0,size = arr.length; i < size; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public static void main(String[] args) {
        FindMedian findMedian = new FindMedian();
        for (int i = 0; i < 500; i++) {
            int[] generator = findMedian.generator(50, 100);
            int[] arr = copyArray(generator);
            int median = findMedian.median(generator);
            Arrays.sort(arr);
            if (arr.length >= 1) {
                if (arr[(arr.length - 1)/2] == median) {
                    System.out.println("good");
                }
            } else {
                System.out.println("good");
            }

        }
    }
}
